{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Tree of Coprimes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getCoprimes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #互质树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n</code> 个节点的树（也就是一个无环连通无向图），节点编号从 <code>0</code> 到 <code>n - 1</code> ，且恰好有 <code>n - 1</code> 条边，每个节点有一个值。树的 <strong>根节点</strong> 为 0 号点。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个二维数组 <code>edges</code> 来表示这棵树。<code>nums[i]</code> 表示第 <code>i</code> 个点的值，<code>edges[j] = [u<sub>j</sub>, v<sub>j</sub>]</code> 表示节点 <code>u<sub>j</sub></code> 和节点 <code>v<sub>j</sub></code> 在树中有一条边。</p>\n",
    "\n",
    "<p>当 <code>gcd(x, y) == 1</code> ，我们称两个数 <code>x</code> 和 <code>y</code> 是 <strong>互质的</strong> ，其中 <code>gcd(x, y)</code> 是 <code>x</code> 和 <code>y</code> 的 <strong>最大公约数</strong> 。</p>\n",
    "\n",
    "<p>从节点 <code>i</code> 到 <strong>根</strong> 最短路径上的点都是节点 <code>i</code> 的祖先节点。一个节点 <strong>不是</strong> 它自己的祖先节点。</p>\n",
    "\n",
    "<p>请你返回一个大小为 <code>n</code> 的数组 <code>ans</code> ，其中<em> </em><code>ans[i]</code>是离节点 <code>i</code> 最近的祖先节点且满足<em> </em><code>nums[i]</code> 和<em> </em><code>nums[ans[i]]</code> 是 <strong>互质的</strong> ，如果不存在这样的祖先节点，<code>ans[i]</code> 为 <code>-1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/02/20/untitled-diagram.png\" style=\"width: 191px; height: 281px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]\n",
    "<b>输出：</b>[-1,0,0,1]\n",
    "<b>解释：</b>上图中，每个节点的值在括号中表示。\n",
    "- 节点 0 没有互质祖先。\n",
    "- 节点 1 只有一个祖先节点 0 。它们的值是互质的（gcd(2,3) == 1）。\n",
    "- 节点 2 有两个祖先节点，分别是节点 1 和节点 0 。节点 1 的值与它的值不是互质的（gcd(3,3) == 3）但节点 0 的值是互质的(gcd(2,3) == 1)，所以节点 0 是最近的符合要求的祖先节点。\n",
    "- 节点 3 有两个祖先节点，分别是节点 1 和节点 0 。它与节点 1 互质（gcd(3,2) == 1），所以节点 1 是离它最近的符合要求的祖先节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/02/20/untitled-diagram1.png\" style=\"width: 441px; height: 291px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]\n",
    "<b>输出：</b>[-1,0,-1,0,0,0,-1]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length == n</code></li>\n",
    "\t<li><code>1 <= nums[i] <= 50</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[j].length == 2</code></li>\n",
    "\t<li><code>0 <= u<sub>j</sub>, v<sub>j</sub> < n</code></li>\n",
    "\t<li><code>u<sub>j</sub> != v<sub>j</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [tree-of-coprimes](https://leetcode.cn/problems/tree-of-coprimes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [tree-of-coprimes](https://leetcode.cn/problems/tree-of-coprimes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,3,2]\\n[[0,1],[1,2],[1,3]]', '[5,6,10,2,3,6,15]\\n[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        # construct the tree\n",
    "        n = len(nums)\n",
    "        graph = defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "        \n",
    "        ans = [-1] * n\n",
    "        upper = [0] * n\n",
    "        \n",
    "        que = [0]\n",
    "        while que:\n",
    "            p = que.pop()\n",
    "            for c in graph[p]:\n",
    "                graph[c].discard(p)\n",
    "                upper[c] = p\n",
    "                que.append(c)\n",
    "\n",
    "        @lru_cache()\n",
    "        def dfs(node:int,num:int)->int:\n",
    "            result = -1\n",
    "            if gcd(nums[node],num)==1:\n",
    "                return node\n",
    "            if node == 0:\n",
    "                return -1\n",
    "            p = upper[node]\n",
    "            result = dfs(p,num)\n",
    "            return result\n",
    "\n",
    "        for i in range(1, n):\n",
    "            ans[i] = dfs(upper[i], nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        # construct the tree\n",
    "        n = len(nums)\n",
    "        graph = defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "        \n",
    "        ans = [-1] * n\n",
    "        upper = [0] * n\n",
    "        \n",
    "        que = [0]\n",
    "        while que:\n",
    "            p = que.pop()\n",
    "            for c in graph[p]:\n",
    "                graph[c].discard(p)\n",
    "                upper[c] = p\n",
    "                que.append(c)\n",
    "\n",
    "        @lru_cache()\n",
    "        def dfs(node:int,num:int)->int:\n",
    "            if gcd(nums[node],num)==1:\n",
    "                return node\n",
    "            if node == 0:\n",
    "                return -1\n",
    "            return dfs(upper[node],num)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            ans[i] = dfs(upper[i], nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        def check(a,b):\n",
    "            a,b=max(a,b),min(a,b)\n",
    "            while b!=0:\n",
    "                a,b=b,a%b\n",
    "            return a==1\n",
    "        n=len(edges)+1\n",
    "        parent=[-1]*n\n",
    "        link_nodes=[[] for i in range(n)]\n",
    "        for [u,v] in edges:\n",
    "            link_nodes[u].append(v)\n",
    "            link_nodes[v].append(u)\n",
    "        q=deque([0])\n",
    "        visited=[False]*n\n",
    "        visited[0]=True\n",
    "        ans=[-1]*n\n",
    "        cnt = 1000\n",
    "        cache=[{} for _ in range(n)]\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                p=parent[node]\n",
    "                trace=[node]\n",
    "                while p!=-1 and not check(nums[p],nums[node]):\n",
    "                    trace.append(p)\n",
    "                    if nums[node] in cache[p]:\n",
    "                        p=cache[p][nums[node]]\n",
    "                        break\n",
    "                    if nums[p]==nums[node]:\n",
    "                        p=ans[p]\n",
    "                        break\n",
    "                    else:\n",
    "                        p=parent[p]\n",
    "                for st in trace:\n",
    "                    cache[st][nums[node]]=p\n",
    "                ans[node]=p\n",
    "                for sub in link_nodes[node]:\n",
    "                    if not visited[sub]:\n",
    "                        q.append(sub)\n",
    "                        visited[sub]=True\n",
    "                        parent[sub]=node\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        def check(a,b):\n",
    "            a,b=max(a,b),min(a,b)\n",
    "            while b!=0:\n",
    "                a,b=b,a%b\n",
    "            return a==1\n",
    "        n=len(edges)+1\n",
    "        parent=[-1]*n\n",
    "        link_nodes=[[] for i in range(n)]\n",
    "        for [u,v] in edges:\n",
    "            link_nodes[u].append(v)\n",
    "            link_nodes[v].append(u)\n",
    "        q=deque([0])\n",
    "        visited=[False]*n\n",
    "        visited[0]=True\n",
    "        ans=[-1]*n\n",
    "        cnt = 1000\n",
    "        cache=[{} for _ in range(n)]\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                p=parent[node]\n",
    "                trace=[node]\n",
    "                while p!=-1 and not check(nums[p],nums[node]):\n",
    "                    trace.append(p)\n",
    "                    if nums[node] in cache[p]:\n",
    "                        p=cache[p][nums[node]]\n",
    "                        break\n",
    "                    else:\n",
    "                        p=parent[p]\n",
    "                for st in trace:\n",
    "                    cache[st][nums[node]]=p\n",
    "                ans[node]=p\n",
    "                for sub in link_nodes[node]:\n",
    "                    if not visited[sub]:\n",
    "                        q.append(sub)\n",
    "                        visited[sub]=True\n",
    "                        parent[sub]=node\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = {x: {y for y in range(1, 51) if gcd(x, y) == 1} for x in range(1, 51)}\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, A: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(A)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        book = defaultdict(list)\n",
    "        res = [-1] * n\n",
    "        stk = []\n",
    "        def dfs(u: int, p=-1):\n",
    "            for y in M[A[u]]:\n",
    "                if book[y] and book[y][-1] > res[u]:\n",
    "                    res[u] = book[y][-1]\n",
    "            \n",
    "            if res[u] != -1:\n",
    "                res[u] = stk[res[u]]\n",
    "                    \n",
    "\n",
    "            book[A[u]].append(len(stk))\n",
    "            stk.append(u)\n",
    "            for v in g[u]:\n",
    "                if v == p: continue\n",
    "                dfs(v, u)\n",
    "            stk.pop()\n",
    "            book[A[u]].pop()\n",
    "        \n",
    "        dfs(0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(nums) \n",
    "        f = [[-1] * 51 for _ in range(n)]\n",
    "        g = defaultdict(list) \n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a) \n",
    "        Q = deque([(0, 0, -1)])\n",
    "        D = [0] * n \n",
    "        while Q:\n",
    "            d, u, fa = Q.popleft() \n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    for i in range(1,51):\n",
    "                        if i == nums[u]:\n",
    "                            f[v][i] = u \n",
    "                        else:\n",
    "                            f[v][i] = f[u][i] \n",
    "                    D[v] = d+1\n",
    "                    Q.append((d+1, v, u))\n",
    "        ans = [-1] * n \n",
    "        for i in range(n):\n",
    "            k = -1 \n",
    "            for j in range(1, 51):\n",
    "                if f[i][j] >= 0:\n",
    "                    x = f[i][j]\n",
    "                    if math.gcd(nums[i], nums[x]) == 1 and (k == -1 or D[k] < D[x]):\n",
    "                        k = x\n",
    "            ans[i] = k \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        # 无向图建树\n",
    "        n = len(nums)\n",
    "        tree = [[] for _ in range(n+1)]\n",
    "        tree[0] = [-1]\n",
    "        for x,y in edges:\n",
    "            tree[x].append(y)\n",
    "            tree[y].append(x)\n",
    "\n",
    "        # 把与nums的数互质的数存起来\n",
    "        g = collections.defaultdict(set)\n",
    "        for j in range(n):\n",
    "            for i in range(51):\n",
    "                if gcd(i, nums[j]) == 1:\n",
    "                    g[nums[j]].add(i)\n",
    "        \n",
    "        # 自底向上搜索\n",
    "        res = [-1] * n\n",
    "        stack = defaultdict(list)\n",
    "        depth = 0\n",
    "        def dfs(root, father):\n",
    "            nonlocal res, depth\n",
    "            # 查找可能存在的最近的互质祖先\n",
    "            ind = -1\n",
    "            recent = -1\n",
    "            for num in g[nums[root]]:\n",
    "                if stack[num] and stack[num][-1][1] > recent:\n",
    "                    ind, recent = stack[num][-1]\n",
    "            res[root] = ind\n",
    "\n",
    "            if len(tree[root]) == 1: return\n",
    "            for child in tree[root]:\n",
    "                if child != father:\n",
    "                    depth += 1\n",
    "                    stack[nums[root]].append((root, depth))\n",
    "                    dfs(child, root)\n",
    "                    depth -= 1\n",
    "                    stack[nums[root]].pop()\n",
    "        dfs(0, -1)\n",
    "        return res\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        # 无向图建树\n",
    "        n = len(nums)\n",
    "        tree = [[] for _ in range(n+1)]\n",
    "        tree[0] = [-1]\n",
    "        for x,y in edges:\n",
    "            tree[x].append(y)\n",
    "            tree[y].append(x)\n",
    "\n",
    "        # 把与nums的数互质的数存起来\n",
    "        g = collections.defaultdict(set)\n",
    "        for j in range(n):\n",
    "            for i in range(51):\n",
    "                if gcd(i, nums[j]) == 1:\n",
    "                    g[nums[j]].add(i)\n",
    "        \n",
    "        # 自底向上搜索\n",
    "        res = [-1] * n\n",
    "        stack = defaultdict(list)\n",
    "        depth = 0\n",
    "        def dfs(root, father):\n",
    "            nonlocal res, depth\n",
    "            # 查找可能存在的最近的互质祖先\n",
    "            ind = -1\n",
    "            recent = -1\n",
    "            for num in g[nums[root]]:\n",
    "                if stack[num] and stack[num][-1][1] > recent:\n",
    "                    ind, recent = stack[num][-1]\n",
    "            res[root] = ind\n",
    "\n",
    "            if len(tree[root]) == 1: return\n",
    "            for child in tree[root]:\n",
    "                if child != father:\n",
    "                    depth += 1\n",
    "                    stack[nums[root]].append((root, depth))\n",
    "                    dfs(child, root)\n",
    "                    depth -= 1\n",
    "                    stack[nums[root]].pop()\n",
    "        dfs(0, -1)\n",
    "        return res\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        gcd = lambda a, b: a if b == 0 else gcd(b, a % b)\n",
    "\n",
    "        dep = [0] * n   # 记录当前节点深度\n",
    "        adjacenties = [[] for _ in range(n)]  # 邻接表\n",
    "        primes = [[] for _ in range(51)]  # 质数数组\n",
    "        pos = [-1] * 51  # 记录dfs路径中最后一个值为1-50的节点的标号\n",
    "        ans = [-1] * n\n",
    "\n",
    "        # 构建邻接表\n",
    "        for u, v in edges:\n",
    "            adjacenties[u].append(v)\n",
    "            adjacenties[v].append(u)\n",
    "        \n",
    "        # 构建质数数组\n",
    "        for i in range(1, 51):\n",
    "            for j in range(1, 51):\n",
    "                if gcd(i, j) == 1:\n",
    "                    primes[i].append(j)\n",
    "        \n",
    "        def dfs(cur, parent):\n",
    "            curVal = nums[cur]\n",
    "            # 根据当前节点的值，遍历对应的质数列表，取深度最大的节点作为答案\n",
    "            for prime in primes[curVal]:\n",
    "                if pos[prime] == -1:\n",
    "                    continue\n",
    "                if ans[cur] == -1 or dep[ans[cur]] < dep[pos[prime]]:\n",
    "                    ans[cur] = pos[prime]\n",
    "            \n",
    "            # 记录上一个当前值对应节点的深度后dfs，当前分支遍历结束后回溯\n",
    "            tmp = pos[curVal]\n",
    "            \n",
    "            pos[curVal] = cur\n",
    "            for adj in adjacenties[cur]:\n",
    "                # 注意邻接节点中有父节点，需要跳过\n",
    "                if adj == parent:\n",
    "                    continue\n",
    "                dep[adj] = dep[cur] + 1\n",
    "                dfs(adj, cur)\n",
    "\n",
    "            pos[curVal] = tmp\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pr=[[] for _ in range(51)]\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if math.gcd(i,j)==1:\n",
    "            pr[i].append(j)\n",
    "            pr[j].append(i)\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        e=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        def dfs(u:int,father:int,tot:int)->None:\n",
    "            idx=-1\n",
    "            now=-1\n",
    "            for x in pr[nums[u]]:\n",
    "                if pre[x] and pre[x][-1][1]>now:\n",
    "                    idx,now=pre[x][-1]\n",
    "            ans[u]=idx\n",
    "            pre[nums[u]].append([u,tot])\n",
    "            for v in e[u]:\n",
    "                if v==father: continue\n",
    "                dfs(v,u,tot+1)\n",
    "            pre[nums[u]].pop(-1)\n",
    "            return\n",
    "        pre=defaultdict(list)\n",
    "        ans=[-1]*n\n",
    "        dfs(0,-1,0)\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pr=[[] for _ in range(51)]\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if math.gcd(i,j)==1:\n",
    "            pr[i].append(j)\n",
    "            pr[j].append(i)\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        e=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        def dfs(u:int,father:int,tot:int)->None:\n",
    "            idx=-1\n",
    "            now=-1\n",
    "            for x in pr[nums[u]]:\n",
    "                if pre[x] and pre[x][-1][1]>now:\n",
    "                    idx,now=pre[x][-1]\n",
    "            ans[u]=idx\n",
    "            pre[nums[u]].append([u,tot])\n",
    "            for v in e[u]:\n",
    "                if v==father: continue\n",
    "                dfs(v,u,tot+1)\n",
    "            pre[nums[u]].pop(-1)\n",
    "            return\n",
    "        pre=defaultdict(list)\n",
    "        ans=[-1]*n\n",
    "        dfs(0,-1,0)\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        p = [[] for _ in range(51)]\n",
    "        for i in range(1, 51):\n",
    "            for j in range(1, 51):\n",
    "                if gcd(i, j) == 1:\n",
    "                    p[i].append(j)\n",
    "        ans = [-1] * n\n",
    "        d = [[-1] * 2 for _ in range(51)]\n",
    "        def dfs(x, fa, deep):\n",
    "            mx = -1\n",
    "            for v in p[nums[x]]:\n",
    "                if d[v][1] > mx:\n",
    "                    mx = d[v][1]\n",
    "                    ans[x] = d[v][0]\n",
    "            t = d[nums[x]]\n",
    "            d[nums[x]] = [x, deep]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x, deep + 1)\n",
    "            d[nums[x]] = t\n",
    "        dfs(0, -1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        gcd = lambda a, b: a if b == 0 else gcd(b, a % b)\n",
    "        # 构建质数数组\n",
    "        primes = [[] for _ in range(51)] \n",
    "        for i in range(1, 51):\n",
    "            for j in range(1, 51):\n",
    "                if gcd(i, j) == 1:primes[i].append(j)\n",
    "\n",
    "        depth = [0] * n   # 记录当前节点深度\n",
    "        adjs = [[] for _ in range(n)]  # 邻接表\n",
    "        pos = [-1] * 51  # 记录dfs路径中最后一个值为1-50的节点的标号\n",
    "        ans = [-1] * n\n",
    "\n",
    "        #1.建树\n",
    "        for u, v in edges:\n",
    "            adjs[u].append(v)\n",
    "            adjs[v].append(u)\n",
    "        \n",
    "        def dfs(cur, parent):\n",
    "            curVal = nums[cur]\n",
    "            # 根据当前节点的值，遍历对应的质数列表，取深度最大的节点作为答案\n",
    "            for prime in primes[curVal]:\n",
    "                if pos[prime] == -1:\n",
    "                    continue\n",
    "                if ans[cur] == -1 or depth[ans[cur]] < depth[pos[prime]]:\n",
    "                    ans[cur] = pos[prime]\n",
    "            \n",
    "            # 记录上一个当前值对应节点的深度后dfs，当前分支遍历结束后回溯\n",
    "            tmp = pos[curVal]\n",
    "            pos[curVal] = cur\n",
    "            for adj in adjs[cur]:\n",
    "                if adj == parent:continue#跳过父节点，防止重复遍历\n",
    "                depth[adj] = depth[cur] + 1\n",
    "                dfs(adj, cur)\n",
    "            pos[curVal] = tmp#撤回\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pr=[[] for _ in range(51)]\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if math.gcd(i,j)==1:\n",
    "            pr[i].append(j)\n",
    "            pr[j].append(i)\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        e=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        def dfs(u:int,father:int,tot:int)->None:\n",
    "            idx=-1\n",
    "            now=-1\n",
    "            for x in pr[nums[u]]:\n",
    "                if pre[x] and pre[x][-1][1]>now:\n",
    "                    idx,now=pre[x][-1]\n",
    "            ans[u]=idx\n",
    "            pre[nums[u]].append([u,tot])\n",
    "            for v in e[u]:\n",
    "                if v==father: continue\n",
    "                dfs(v,u,tot+1)\n",
    "            pre[nums[u]].pop(-1)\n",
    "            return\n",
    "        pre=defaultdict(list)\n",
    "        ans=[-1]*n\n",
    "        dfs(0,-1,0)\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pr=[[] for _ in range(51)]\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if math.gcd(i,j)==1:\n",
    "            pr[i].append(j)\n",
    "            pr[j].append(i)\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        e=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        def dfs(u:int,father:int,tot:int)->None:\n",
    "            idx=-1\n",
    "            now=-1\n",
    "            for x in pr[nums[u]]:\n",
    "                if pre[x] and pre[x][-1][1]>now:\n",
    "                    idx,now=pre[x][-1]\n",
    "            ans[u]=idx\n",
    "            pre[nums[u]].append([u,tot])\n",
    "            for v in e[u]:\n",
    "                if v==father: continue\n",
    "                dfs(v,u,tot+1)\n",
    "            pre[nums[u]].pop(-1)\n",
    "            return\n",
    "        pre=defaultdict(list)\n",
    "        ans=[-1]*n\n",
    "        dfs(0,-1,0)\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "hashmap = defaultdict(set)\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if gcd(i,j) == 1:\n",
    "            hashmap[i].add(j)\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        visited = defaultdict(lambda :-1)\n",
    "        deeps = defaultdict(lambda :-1)\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        for u , v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        ans = [-1] * len(nums)\n",
    "\n",
    "        def dfs(node,parent,deep):\n",
    "            max_deep = -1\n",
    "            for x in hashmap[nums[node]]:\n",
    "                if visited[x] != -1 and deeps[x] > max_deep:\n",
    "                    ans[node] = visited[x]\n",
    "                    max_deep = deeps[x]\n",
    "            td = deeps[nums[node]]\n",
    "            deeps[nums[node]] = deep\n",
    "            t = visited[nums[node]]\n",
    "            visited[nums[node]] = node\n",
    "            for nxt in graph[node]:\n",
    "                if nxt != parent:\n",
    "                    dfs(nxt,node,deep+1)\n",
    "            visited[nums[node]] = t\n",
    "            deeps[nums[node]] = td\n",
    "\n",
    "        dfs(0,-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 50\n",
    "coprime = [[False] * (MX+1) for _ in range(MX+1)]\n",
    "for a in range(1, MX+1):\n",
    "    for b in range(a, MX+1):\n",
    "        coprime[a][b] = coprime[b][a] = gcd(a, b) == 1\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        ancestors = [[] for _ in range(MX+1)]  # ancestors[val]: (x, depth)\n",
    "        ans = [-1] * n\n",
    "        def dfs(x, pa, depth):\n",
    "            maxd = -1\n",
    "            res = -1\n",
    "            for val, ancestor in enumerate(ancestors):\n",
    "                if not ancestor:\n",
    "                    continue\n",
    "                target, d = ancestor[-1]\n",
    "                if coprime[nums[x]][val] and d > maxd:\n",
    "                    maxd = d\n",
    "                    res = target\n",
    "            ans[x] = res\n",
    "            ancestors[nums[x]].append((x, depth))\n",
    "            for y in g[x]:\n",
    "                if y == pa:\n",
    "                    continue\n",
    "                dfs(y, x, depth+1)\n",
    "            ancestors[nums[x]].pop()\n",
    "\n",
    "        dfs(0, -1, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        # print(g)\n",
    "        ans = [-1] * n\n",
    "        d = defaultdict(list)\n",
    "        d[nums[0]].append((0, 0))\n",
    "        time = 0\n",
    "        def dfs(u, fa, ti):\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    cur = tmp = float('-inf')\n",
    "                    for num in d:\n",
    "                        if d[num]:\n",
    "                            if gcd(num, nums[v]) == 1:\n",
    "                                if d[num][-1][1] >= tmp:\n",
    "                                    tmp = d[num][-1][1]\n",
    "                                    cur = d[num][-1][0]\n",
    "\n",
    "                    if cur != float('-inf'):\n",
    "                        ans[v] = cur\n",
    "                    d[nums[v]].append((v, ti))\n",
    "                    dfs(v, u, ti + 1)\n",
    "                    d[nums[v]].pop()\n",
    "        \n",
    "        dfs(0, -1, 0)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        f = [0] * n\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            \n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "        \n",
    "        flag = [[0] * 51 for _ in range(51)]\n",
    "        for i in range(1, 51):\n",
    "            for j in range(i, 51):\n",
    "                flag[i][j] = flag[j][i] = gcd(i, j) == 1\n",
    "                \n",
    "        ret = [-1] * n       \n",
    "        def dfs(node, fa, mask, path, cnt):\n",
    "            x = nums[node]\n",
    "            idx = -1\n",
    "            for i in range(1, 51):\n",
    "                if mask & 1 << i and flag[x][i] and (idx == -1 or path[i][1] > path[idx][1]):\n",
    "                    idx = i\n",
    "            if idx != -1:\n",
    "                ret[node] = path[idx][0]\n",
    "                \n",
    "            cnt += 1\n",
    "            \n",
    "            tmp = path[x]\n",
    "            path[x] = (node, cnt)\n",
    "            \n",
    "                                           \n",
    "            mask |= 1 << nums[node]\n",
    "            for son in g[node]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                # f[son] = mask\n",
    "                dfs(son, node, mask, path, cnt)\n",
    "            path[x] = tmp\n",
    "        \n",
    "        dfs(0, -1, 0, [(-1, -1) for _ in range(51)], 0)\n",
    "        return ret\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pr=[[] for _ in range(51)]\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if math.gcd(i,j)==1:\n",
    "            pr[i].append(j)\n",
    "            pr[j].append(i)\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        e=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        def dfs(u,tot):\n",
    "            idx=-1\n",
    "            now=-1\n",
    "            for x in pr[nums[u]]:\n",
    "                if pre[x] and pre[x][-1][1]>now:\n",
    "                    idx,now=pre[x][-1]\n",
    "            ans[u]=idx\n",
    "            pre[nums[u]].append([u,tot])\n",
    "            vis[u]=1\n",
    "            for v in e[u]:\n",
    "                if not vis[v]:\n",
    "                    dfs(v,tot+1)\n",
    "            pre[nums[u]].pop(-1)\n",
    "            vis[u]=0\n",
    "            return\n",
    "        pre=defaultdict(list)\n",
    "        vis=[0]*n\n",
    "        vis[0]=1\n",
    "        ans=[-1]*n\n",
    "        dfs(0,0)\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import defaultdict\n",
    "\n",
    "prime_pair = [[] for _ in range(51)]\n",
    "for x in range(1, 51):\n",
    "    for y in range(x, 51):\n",
    "        if math.gcd(x, y) == 1:\n",
    "            prime_pair[x].append(y)\n",
    "            prime_pair[y].append(x)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        # 记录拓扑关系\n",
    "        n = len(nums)\n",
    "        edge = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            edge[u].append(v)\n",
    "            edge[v].append(u)\n",
    "\n",
    "        def dfs(root, order):\n",
    "            # 查找可能存在的最近的互质祖先\n",
    "            ind = -1\n",
    "            recent = -1\n",
    "            for num in prime_pair[nums[root]]:\n",
    "                if pre[num] and pre[num][-1][1] > recent:\n",
    "                    ind, recent = pre[num][-1]\n",
    "            ans[root] = ind\n",
    "            # 将当前的节点信息加入到祖先序列\n",
    "            pre[nums[root]].append([root, order])\n",
    "            visit[root] = 1\n",
    "            for son in edge[root]:\n",
    "                if not visit[son]:\n",
    "                    dfs(son, order+1)\n",
    "            # 回溯将此时的节点信息清除\n",
    "            pre[nums[root]].pop(-1)\n",
    "            visit[root] = 0\n",
    "            return\n",
    "\n",
    "        # 哈希记录前序祖先的值与搜索深度序号\n",
    "        pre = defaultdict(list)\n",
    "        # 深度优先搜索\n",
    "        visit = [0]*n\n",
    "        visit[0] = 1\n",
    "        ans = [-1]*n\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        # print(g)\n",
    "        ans = [-1] * n\n",
    "        d = defaultdict(list)\n",
    "        d[nums[0]].append((0, 0))\n",
    "        def dfs(u, fa, ti):\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    cur = tmp = float('-inf')\n",
    "                    for num in d:\n",
    "                        if d[num]:\n",
    "                            if gcd(num, nums[v]) == 1:\n",
    "                                if d[num][-1][1] >= tmp:\n",
    "                                    tmp = d[num][-1][1]\n",
    "                                    cur = d[num][-1][0]\n",
    "\n",
    "                    if cur != float('-inf'):\n",
    "                        ans[v] = cur\n",
    "                    d[nums[v]].append((v, ti + 1))\n",
    "                    dfs(v, u, ti + 1)\n",
    "                    d[nums[v]].pop()\n",
    "        \n",
    "        dfs(0, -1, 0)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        # print(g)\n",
    "        ans = [-1] * n\n",
    "        d = defaultdict(list)\n",
    "        d[nums[0]].append((0, 0))\n",
    "        def dfs(u, fa, ti):\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    cur = tmp = float('-inf')\n",
    "                    for num in d:\n",
    "                        if d[num]:\n",
    "                            if gcd(num, nums[v]) == 1:\n",
    "                                if d[num][-1][1] > tmp:\n",
    "                                    tmp = d[num][-1][1]\n",
    "                                    cur = d[num][-1][0]\n",
    "\n",
    "                    if cur != float('-inf'):\n",
    "                        ans[v] = cur\n",
    "                    d[nums[v]].append((v, ti + 1))\n",
    "                    dfs(v, u, ti + 1)\n",
    "                    d[nums[v]].pop()\n",
    "        \n",
    "        dfs(0, -1, 0)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "gd = defaultdict(list)\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if gcd(i,j) == 1:\n",
    "            gd[i].append(j)\n",
    "            gd[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n\n",
    "        g = defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        path = defaultdict(list)\n",
    "        def dfs(u,fa,depth):\n",
    "            idx = dis = -1\n",
    "            for x in gd[nums[u]]:\n",
    "                if path[x] and path[x][-1][1] > dis:\n",
    "                    idx,dis = path[x][-1]\n",
    "            ans[u] = idx\n",
    "            path[nums[u]].append((u,depth))\n",
    "            for v in g[u]:\n",
    "                if v == fa:\n",
    "                    continue\n",
    "                dfs(v,u,depth + 1)\n",
    "            path[nums[u]].pop()\n",
    "        \n",
    "        dfs(0,-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "gd = defaultdict(list)\n",
    "for i in range(1,51):\n",
    "    for j in range(i,51):\n",
    "        if gcd(i,j) == 1:\n",
    "            gd[i].append(j)\n",
    "            gd[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        # n个节点，n - 1条边，无环连通无向图 =》 根节点到任意节点都只有一条路，就是最短路\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        path = defaultdict(list) # 记录路径上经过的数字和对应深度\n",
    "        \n",
    "        def dfs(u,fa,depth):\n",
    "            # 找root的可能的最近祖先\n",
    "            idx = dis = -1\n",
    "            for x in gd[nums[u]]:\n",
    "                if path[x] and path[x][-1][1] > dis:\n",
    "                    idx,dis = path[x][-1]\n",
    "            ans[u] = idx\n",
    "            path[nums[u]].append((u,depth))\n",
    "            for v in g[u]:\n",
    "                if v == fa:\n",
    "                    continue\n",
    "                dfs(v,u,depth + 1)\n",
    "            path[nums[u]].pop()\n",
    "\n",
    "        dfs(0,-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        con = [[] for i in range(51)]\n",
    "\n",
    "        for i in range(1, 51):\n",
    "            for j in range(i, 51):\n",
    "                if math.gcd(i, j) == 1:\n",
    "                    con[i].append(j)\n",
    "                    con[j].append(i)\n",
    "        test = [[] for i in range(len(nums))]\n",
    "        for i in range(len(edges)):\n",
    "            test[edges[i][0]].append(edges[i][1])\n",
    "            test[edges[i][1]].append(edges[i][0])\n",
    "        ans = [-1 for i in range(len(nums))]\n",
    "        ref = [[] for i in range(51)]\n",
    "        vis = set()\n",
    "        def dfs(node, depth):\n",
    "            res = -1\n",
    "            x = -1\n",
    "            for i in con[nums[node]]:\n",
    "                if ref[i]:\n",
    "                    if ref[i][-1][0] > x:\n",
    "                        res = ref[i][-1][1]\n",
    "                        x = ref[i][-1][0]\n",
    "            ans[node] = res\n",
    "            ref[nums[node]].append((depth, node))\n",
    "            vis.add(node)\n",
    "            for i in test[node]:\n",
    "                if i not in vis:\n",
    "                    dfs(i, depth + 1)\n",
    "            ref[nums[node]].pop()\n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        g=defaultdict(list)\n",
    "        for i,v in edges:\n",
    "            g[i].append(v)\n",
    "            g[v].append(i)\n",
    "\n",
    "        prime=defaultdict(set)\n",
    "        for i in range(1,51):\n",
    "            for j in range(1,51):\n",
    "                if gcd(i,j)==1:\n",
    "                    prime[i].add(j)\n",
    "        \n",
    "        n=len(nums)\n",
    "        f=defaultdict(list)\n",
    "        res=[-1]*n\n",
    "        def dfs(u,fa,depth):\n",
    "            # print(u,fa,depth,nums[u])\n",
    "            f[nums[u]].append((u,depth))\n",
    "            for v in g[u]:\n",
    "                if v==fa:continue\n",
    "                dfs(v,u,depth+1)\n",
    "            f[nums[u]].pop()\n",
    "          \n",
    "            # print(u,f)\n",
    "            mx= -1\n",
    "            ans= -1\n",
    "            for v in prime[nums[u]]:\n",
    "                # print(\"u:\",u,nums[u],v,f[v])\n",
    "                if v in f and f[v]:\n",
    "                    root,dep=f[v][-1]\n",
    "                    if mx<dep:\n",
    "                        ans=root\n",
    "                        mx=dep\n",
    "            res[u]=ans\n",
    "           \n",
    "            \n",
    "        dfs(0,-1,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        import math\n",
    "        from collections import defaultdict\n",
    "        dic = {}\n",
    "        for i in range(1,51):\n",
    "            dic[i] = []\n",
    "            for j in range(1,51):\n",
    "                if math.gcd(i,j) == 1:\n",
    "                    dic[i].append(j)\n",
    "        pos = [-1]*52\n",
    "        depths = [-1]*len(nums)\n",
    "        transfer_edges = defaultdict(list)\n",
    "        res = [-1]*len(nums)\n",
    "        for u,v in edges:\n",
    "            transfer_edges[u].append(v)\n",
    "            transfer_edges[v].append(u)\n",
    "        def dfs(nums,u,prev):\n",
    "            n = nums[u]\n",
    "            for m in dic[n]:\n",
    "                if pos[m] == -1:\n",
    "                    continue\n",
    "                if res[u] == -1 or (depths[res[u]] < depths[pos[m]]):\n",
    "                    res[u] = pos[m]\n",
    "            t = pos[n]\n",
    "            pos[n] = u\n",
    "            for v in transfer_edges[u]:\n",
    "                if v == prev:\n",
    "                    continue\n",
    "                depths[v] = depths[u] + 1\n",
    "                dfs(nums,v,u)\n",
    "            pos[n] = t\n",
    "        dfs(nums,0,-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        # 建图\n",
    "        table = collections.defaultdict(list)\n",
    "        table[0] = [-1]     # 根节点特殊处理\n",
    "        for a, b in edges:\n",
    "            table[a].append(b)\n",
    "            table[b].append(a)\n",
    "\n",
    "        # 构建互质表\n",
    "        nums_set = set(nums)\n",
    "        coprimer_dic = dict()\n",
    "        for i in nums_set:\n",
    "            coprimer_dic[i] = set(num for num in nums_set if math.gcd(i, num) == 1)\n",
    "        # print(coprimer_dic)\n",
    "        # 构建储存互质父节点的哈希表\n",
    "        recent_coprimer_table = collections.defaultdict(list)\n",
    "        ans = [-1] * n\n",
    "        def dfs(node, father):\n",
    "            # node的值num\n",
    "            num = nums[node]\n",
    "            # node最近的互质父节点，储存在recent_coprimer_table[num]的栈顶\n",
    "            ans[node] = recent_coprimer_table[num][-1] if recent_coprimer_table[num] else -1\n",
    "            \n",
    "            # 终止条件，遇到叶节点\n",
    "            if len(table[node]) == 1:\n",
    "                return\n",
    "\n",
    "            for child in table[node]:\n",
    "\n",
    "                # 状态更新\n",
    "                # 所有和num互质的数coprimer\n",
    "                for coprimer in coprimer_dic[num]:\n",
    "                    # node将和之后出现的，值为coprimer的节点互质\n",
    "                    recent_coprimer_table[coprimer].append(node)\n",
    "                    \n",
    "                # 无向图，特殊判断\n",
    "                if child != father:\n",
    "                    dfs(child, node)\n",
    "            \n",
    "                # 回滚\n",
    "                for coprimer in coprimer_dic[num]:\n",
    "                    # node将和之后出现的，值为coprimer的节点互质\n",
    "                    recent_coprimer_table[coprimer].pop()\n",
    "        \n",
    "        # 递归入口\n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        # 建图\n",
    "        table = collections.defaultdict(list)\n",
    "        table[0] = [-1]     # 根节点特殊处理\n",
    "        for a, b in edges:\n",
    "            table[a].append(b)\n",
    "            table[b].append(a)\n",
    "\n",
    "        # 构建互质表\n",
    "        nums_set = set(nums)\n",
    "        coprimer_dic = dict()\n",
    "        for i in nums_set:\n",
    "            coprimer_dic[i] = set(num for num in nums_set if math.gcd(i, num) == 1)\n",
    "        # print(coprimer_dic)\n",
    "        # 构建储存互质父节点的哈希表\n",
    "        recent_coprimer_table = collections.defaultdict(list)\n",
    "        ans = [-1] * n\n",
    "        def dfs(node, father):\n",
    "            # node的值num\n",
    "            num = nums[node]\n",
    "            # node最近的互质父节点，储存在recent_coprimer_table[num]的栈顶\n",
    "            ans[node] = recent_coprimer_table[num][-1] if recent_coprimer_table[num] else -1\n",
    "            \n",
    "            # 终止条件，遇到叶节点\n",
    "            if len(table[node]) == 1:\n",
    "                return\n",
    "\n",
    "            for child in table[node]:\n",
    "                # 所有和num互质的数coprimer\n",
    "                for coprimer in coprimer_dic[num]:\n",
    "                    # node将和之后出现的，值为coprimer的节点互质\n",
    "                    recent_coprimer_table[coprimer].append(node)\n",
    "                    \n",
    "                # 无向图，特殊判断\n",
    "                if child != father:\n",
    "                    dfs(child, node)\n",
    "            \n",
    "                # 回滚\n",
    "                for coprimer in coprimer_dic[num]:\n",
    "                    # node将和之后出现的，值为coprimer的节点互质\n",
    "                    recent_coprimer_table[coprimer].pop()\n",
    "\n",
    "        \n",
    "        # 递归入口\n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        gd = defaultdict(list)\n",
    "        for i in range(1,51):\n",
    "            for j in range(1,51):\n",
    "                if gcd(i,j) == 1:\n",
    "                    gd[i].append(j)\n",
    "                    gd[j].append(i)\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        ans = [-1]*len(nums)\n",
    "        path = defaultdict(list)\n",
    "        def dfs(u,fa,d):\n",
    "            idx = dis = -1\n",
    "            for x in gd[nums[u]]:\n",
    "                if path[x] and path[x][-1][1] > dis:\n",
    "                    idx,dis = path[x][-1]\n",
    "            ans[u] = idx\n",
    "            path[nums[u]].append((u,d))\n",
    "            for v in g[u]:\n",
    "                if v == fa:\n",
    "                    continue\n",
    "                dfs(v,u,d + 1)\n",
    "            path[nums[u]].pop()\n",
    "        dfs(0,-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from math import gcd\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        # 构建邻接列表来表示树\n",
    "        tree = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            tree[u].append(v)\n",
    "            tree[v].append(u)\n",
    "        \n",
    "        # ans 存储每个节点的结果\n",
    "        ans = [-1] * len(nums)\n",
    "        \n",
    "        # ancestors 用于存储每种数值的最近祖先节点和深度\n",
    "        # 格式：{value: [(node, depth), ...]}\n",
    "        ancestors = defaultdict(list)\n",
    "        \n",
    "        def dfs(node, parent, depth):\n",
    "            nonlocal tree, nums, ans, ancestors\n",
    "            \n",
    "            # 查找最近的互质祖先\n",
    "            closest_ancestor = -1\n",
    "            closest_depth = -1\n",
    "            for value, stack in ancestors.items():\n",
    "                if gcd(nums[node], value) == 1:\n",
    "                    if stack:\n",
    "                        ancestor, ancestor_depth = stack[-1]\n",
    "                        if closest_ancestor == -1 or ancestor_depth > closest_depth:\n",
    "                            closest_ancestor = ancestor\n",
    "                            closest_depth = ancestor_depth\n",
    "            \n",
    "            ans[node] = closest_ancestor\n",
    "            \n",
    "            # 添加当前节点到其数值对应的祖先列表\n",
    "            ancestors[nums[node]].append((node, depth))\n",
    "            \n",
    "            # 遍历子节点\n",
    "            for child in tree[node]:\n",
    "                if child == parent:\n",
    "                    continue\n",
    "                dfs(child, node, depth + 1)\n",
    "            \n",
    "            # 回溯：从祖先列表中移除当前节点\n",
    "            ancestors[nums[node]].pop()\n",
    "        \n",
    "        dfs(0, -1, 0)\n",
    "        return ans\n",
    "\n",
    "# 测试\n",
    "nums = [9,16,30,23,33,35,9,47,39,46,16,38,5,49,21,44,17,1,6,37,49,15,23,46,38,9,27,3,24,1,14,17,12,23,43,38,12,4,8,17,11,18,26,22,49,14,9]\n",
    "edges = [[17,0],[30,17],[41,30],[10,30],[13,10],[7,13],[6,7],[45,10],[2,10],[14,2],[40,14],[28,40],[29,40],[8,29],[15,29],[26,15],[23,40],[19,23],[34,19],[18,23],[42,18],[5,42],[32,5],[16,32],[35,14],[25,35],[43,25],[3,43],[36,25],[38,36],[27,38],[24,36],[31,24],[11,31],[39,24],[12,39],[20,12],[22,12],[21,39],[1,21],[33,1],[37,1],[44,37],[9,44],[46,2],[4,46]]\n",
    "\n",
    "sol = Solution()\n",
    "print(sol.getCoprimes(nums, edges))  # 预期结果\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        def gcd(x,y):\n",
    "            if y == 0:\n",
    "                return x\n",
    "            return gcd(y, x % y)\n",
    "        chart = {_:[] for _ in range(1,51)}\n",
    "        \n",
    "        for i in range(1,51):\n",
    "            for j in range(i+1,51):\n",
    "                if gcd(i,j) == 1:\n",
    "                    chart[i].append(j)\n",
    "                    chart[j].append(i)\n",
    "        chart[1].append(1) # 1 1 互质\n",
    "        n = len(nums)\n",
    "        edge_table = {_:[] for _ in range(n)}\n",
    "        for edge in edges:\n",
    "            edge_table[edge[0]].append(edge[1])\n",
    "            edge_table[edge[1]].append(edge[0])\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        def dfs(x,hash_stack,depth,now_d,father):\n",
    "            d = -1\n",
    "            value = nums[x]\n",
    "            for s in chart[value]:\n",
    "                if s in hash_stack:\n",
    "                    if depth[s] > d:\n",
    "                        d = depth[s]\n",
    "                        ans[x] = hash_stack[s]\n",
    "            if value in hash_stack:\n",
    "                old_x = hash_stack[value]\n",
    "                old_d = depth[value]\n",
    "            else:\n",
    "                old_x = -1\n",
    "                old_d = -1\n",
    "            hash_stack[value] = x\n",
    "            depth[value] = now_d\n",
    "            for y in edge_table[x]:\n",
    "                if y == father:\n",
    "                    continue\n",
    "                dfs(y,hash_stack,depth,now_d+1,x)\n",
    "            if old_x == -1:\n",
    "                del hash_stack[value]\n",
    "                del depth[value]\n",
    "            else:\n",
    "                hash_stack[value] = old_x\n",
    "                depth[value] = old_d\n",
    "        dfs(0,{},{},1,0)\n",
    "        return ans\n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        def gcd(x,y):\n",
    "            if y == 0:\n",
    "                return x\n",
    "            return gcd(y, x % y)\n",
    "        chart = {_:[] for _ in range(1,51)}\n",
    "        \n",
    "        for i in range(1,51):\n",
    "            for j in range(i+1,51):\n",
    "                if gcd(i,j) == 1:\n",
    "                    chart[i].append(j)\n",
    "                    chart[j].append(i)\n",
    "        chart[1].append(1) # 1 1 互质\n",
    "        n = len(nums)\n",
    "        edge_table = {_:[] for _ in range(n)}\n",
    "        for edge in edges:\n",
    "            edge_table[edge[0]].append(edge[1])\n",
    "            edge_table[edge[1]].append(edge[0])\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        del n\n",
    "        def dfs(x,hash_stack,depth,now_d,father):\n",
    "            d = -1\n",
    "            value = nums[x]\n",
    "            for s in chart[value]:\n",
    "                if s in hash_stack:\n",
    "                    if depth[s] > d:\n",
    "                        d = depth[s]\n",
    "                        ans[x] = hash_stack[s]\n",
    "            if value in hash_stack:\n",
    "                old_x = hash_stack[value]\n",
    "                old_d = depth[value]\n",
    "            else:\n",
    "                old_x = -1\n",
    "                old_d = -1\n",
    "            hash_stack[value] = x\n",
    "            depth[value] = now_d\n",
    "            for y in edge_table[x]:\n",
    "                if y == father:\n",
    "                    continue\n",
    "                dfs(y,hash_stack,depth,now_d+1,x)\n",
    "            if old_x == -1:\n",
    "                del hash_stack[value]\n",
    "                del depth[value]\n",
    "            else:\n",
    "                hash_stack[value] = old_x\n",
    "                depth[value] = old_d\n",
    "        dfs(0,{},{},1,0)\n",
    "        return ans\n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        def gcd(x,y):\n",
    "            if y == 0:\n",
    "                return x\n",
    "            return gcd(y, x % y)\n",
    "        chart = {_:[] for _ in range(1,51)}\n",
    "        \n",
    "        for i in range(1,51):\n",
    "            for j in range(i+1,51):\n",
    "                if gcd(i,j) == 1:\n",
    "                    chart[i].append(j)\n",
    "                    chart[j].append(i)\n",
    "        chart[1].append(1) # 1 1 互质\n",
    "        n = len(nums)\n",
    "        edge_table = {_:[] for _ in range(n)}\n",
    "        for edge in edges:\n",
    "            edge_table[edge[0]].append(edge[1])\n",
    "            edge_table[edge[1]].append(edge[0])\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        def dfs(x,hash_stack,depth,now_d,father):\n",
    "            d = -1\n",
    "            value = nums[x]\n",
    "            for s in chart[value]:\n",
    "                if s in hash_stack and hash_stack[s] != -1:\n",
    "                    if depth[s] > d:\n",
    "                        d = depth[s]\n",
    "                        ans[x] = hash_stack[s]\n",
    "            if value in hash_stack:\n",
    "                old_x = hash_stack[value]\n",
    "                old_d = depth[value]\n",
    "            else:\n",
    "                old_x = -1\n",
    "                old_d = -1\n",
    "            hash_stack[value] = x\n",
    "            depth[value] = now_d\n",
    "            for y in edge_table[x]:\n",
    "                if y == father:\n",
    "                    continue\n",
    "                dfs(y,hash_stack,depth,now_d+1,x)\n",
    "            hash_stack[value] = old_x\n",
    "            depth[value] = old_d\n",
    "        dfs(0,{},{},1,0)\n",
    "        return ans\n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        graph = collections.defaultdict(list)\n",
    "\n",
    "        for edge in edges:\n",
    "            i, j = edge\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "\n",
    "        stacks = [[] for _ in range(51)]\n",
    "        res = [-1 for i in range(len(nums))]\n",
    "\n",
    "        def dfs(node, parent, depth):\n",
    "            candidates = []\n",
    "            for i in range(1, len(stacks)):\n",
    "                if len(stacks[i]) > 0 and math.gcd(i, nums[node]) == 1:\n",
    "                    candidates.append(stacks[i][-1])\n",
    "\n",
    "            maxDepth = -1\n",
    "            resNode = -1\n",
    "            for candidate in candidates:\n",
    "                d, n = candidate\n",
    "                if d > maxDepth:\n",
    "                    maxDepth = d\n",
    "                    resNode = n\n",
    "            res[node] = resNode\n",
    "\n",
    "            stacks[nums[node]].append((depth, node))\n",
    "\n",
    "            children = graph[node]\n",
    "            for child in children:\n",
    "                if child != parent:\n",
    "                    dfs(child, node, depth + 1)\n",
    "            stacks[nums[node]].pop()\n",
    "\n",
    "        dfs(0, None, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PREME=[set() for _ in range(51)]\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if math.gcd(i,j)==1:\n",
    "            PREME[i].add(j)\n",
    "# print(PREME)\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        buff=defaultdict(list)\n",
    "        n=len(nums)\n",
    "        parent=[-1]*n\n",
    "        for [u,v] in edges:\n",
    "            buff[u].append(v)\n",
    "            buff[v].append(u)\n",
    "        edges=buff\n",
    "        edges=defaultdict(list)\n",
    "        visited=[False]*n\n",
    "        q=deque([0])\n",
    "        while q:\n",
    "            u=q.popleft()\n",
    "            visited[u]=True\n",
    "            for v in buff[u]:\n",
    "                if not visited[v]:\n",
    "                    edges[u].append(v)\n",
    "                    q.append(v)\n",
    "        ans=[-1]*n\n",
    "        def dfs(node,trace,depth):\n",
    "            val=nums[node]\n",
    "            tmp=-1\n",
    "            for could in PREME[val]:\n",
    "                if trace[could]:\n",
    "                    parent_node,d=trace[could][-1]\n",
    "                    if d>tmp:\n",
    "                        ans[node]=parent_node\n",
    "                        tmp=d\n",
    "                    if d==depth-1:\n",
    "                        break\n",
    "            trace[val].append((node,depth))\n",
    "            for sub in edges[node]:\n",
    "                dfs(sub,trace,depth+1)\n",
    "            trace[val].pop()\n",
    "        dfs(0,[[] for _ in range(51)],0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PREME=[set() for _ in range(51)]\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if math.gcd(i,j)==1:\n",
    "            PREME[i].add(j)\n",
    "# print(PREME)\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        buff=defaultdict(list)\n",
    "        n=len(nums)\n",
    "        parent=[-1]*n\n",
    "        for [u,v] in edges:\n",
    "            buff[u].append(v)\n",
    "            buff[v].append(u)\n",
    "        edges=buff\n",
    "        edges=defaultdict(list)\n",
    "        visited=[False]*n\n",
    "        q=deque([0])\n",
    "        while q:\n",
    "            u=q.popleft()\n",
    "            visited[u]=True\n",
    "            for v in buff[u]:\n",
    "                if not visited[v]:\n",
    "                    edges[u].append(v)\n",
    "                    q.append(v)\n",
    "        ans=[-1]*n\n",
    "        def dfs(node,trace,depth):\n",
    "            val=nums[node]\n",
    "            tmp=-1\n",
    "            for could in PREME[val]:\n",
    "                if trace[could]:\n",
    "                    parent_node,d=trace[could][-1]\n",
    "                    if d>tmp:\n",
    "                        ans[node]=parent_node\n",
    "                        tmp=d\n",
    "            trace[val].append((node,depth))\n",
    "            for sub in edges[node]:\n",
    "                dfs(sub,trace,depth+1)\n",
    "            trace[val].pop()\n",
    "        dfs(0,[[] for _ in range(51)],0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PREME=[set() for _ in range(51)]\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if math.gcd(i,j)==1:\n",
    "            PREME[i].add(j)\n",
    "# print(PREME)\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        buff=defaultdict(list)\n",
    "        n=len(nums)\n",
    "        for [u,v] in edges:\n",
    "            buff[u].append(v)\n",
    "            buff[v].append(u)\n",
    "        edges=buff\n",
    "        edges=defaultdict(list)\n",
    "        visited=[False]*n\n",
    "        q=deque([0])\n",
    "        parent=[-1]*n\n",
    "        while q:\n",
    "            u=q.popleft()\n",
    "            visited[u]=True\n",
    "            for v in buff[u]:\n",
    "                if not visited[v]:\n",
    "                    parent[v]=u\n",
    "                    edges[u].append(v)\n",
    "                    q.append(v)\n",
    "        ans=[-1]*n\n",
    "        def dfs(node,trace,depth):\n",
    "            val=nums[node]\n",
    "            if val==1:\n",
    "                ans[node]=parent[node]\n",
    "            else:\n",
    "                tmp=-1\n",
    "                for could in PREME[val]:\n",
    "                    if trace[could]:\n",
    "                        parent_node,d=trace[could][-1]\n",
    "                        if d>tmp:\n",
    "                            ans[node]=parent_node\n",
    "                            tmp=d\n",
    "                        if d==depth-1:\n",
    "                            break\n",
    "            trace[val].append((node,depth))\n",
    "            for sub in edges[node]:\n",
    "                dfs(sub,trace,depth+1)\n",
    "            trace[val].pop()\n",
    "        dfs(0,[[] for _ in range(51)],0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PREME=[set() for _ in range(51)]\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if math.gcd(i,j)==1:\n",
    "            PREME[i].add(j)\n",
    "# print(PREME)\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        buff=defaultdict(list)\n",
    "        n=len(nums)\n",
    "        parent=[-1]*n\n",
    "        for [u,v] in edges:\n",
    "            buff[u].append(v)\n",
    "            buff[v].append(u)\n",
    "        edges=buff\n",
    "        edges=defaultdict(list)\n",
    "        visited=[False]*n\n",
    "        q=deque([0])\n",
    "        while q:\n",
    "            u=q.popleft()\n",
    "            visited[u]=True\n",
    "            for v in buff[u]:\n",
    "                if not visited[v]:\n",
    "                    edges[u].append(v)\n",
    "                    q.append(v)\n",
    "        # print('edges',edges)\n",
    "        ans=[-1]*n\n",
    "        def dfs(node,trace,depth):\n",
    "            val=nums[node]\n",
    "            tmp=-1\n",
    "            # print(depth,node,trace)\n",
    "            for could in PREME[val]:\n",
    "                if trace[could]:\n",
    "                    parent_node,d=trace[could][-1]\n",
    "                    if d>tmp:\n",
    "                        ans[node]=parent_node\n",
    "                        tmp=d\n",
    "            trace[val].append((node,depth))\n",
    "            for sub in edges[node]:\n",
    "                dfs(sub,trace,depth+1)\n",
    "            trace[val].pop()\n",
    "        dfs(0,[[] for _ in range(51)],0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PREME=[set() for _ in range(51)]\n",
    "for i in range(1,51):\n",
    "    for j in range(1,51):\n",
    "        if math.gcd(i,j)==1:\n",
    "            PREME[i].add(j)\n",
    "# print(PREME)\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        buff=defaultdict(list)\n",
    "        n=len(nums)\n",
    "        parent=[-1]*n\n",
    "        for [u,v] in edges:\n",
    "            buff[u].append(v)\n",
    "            buff[v].append(u)\n",
    "        edges=buff\n",
    "        edges=defaultdict(list)\n",
    "        visited=[False]*n\n",
    "        q=deque([0])\n",
    "        while q:\n",
    "            u=q.popleft()\n",
    "            visited[u]=True\n",
    "            for v in buff[u]:\n",
    "                if not visited[v]:\n",
    "                    edges[u].append(v)\n",
    "                    q.append(v)\n",
    "        ans=[-1]*n\n",
    "        def dfs(node,trace,depth):\n",
    "            val=nums[node]\n",
    "            tmp=-1\n",
    "            for could in PREME[val]:\n",
    "                if trace[could]:\n",
    "                    parent_node,d=trace[could][-1]\n",
    "                    if d>tmp:\n",
    "                        ans[node]=parent_node\n",
    "                        tmp=d\n",
    "            trace[val].append((node,depth))\n",
    "            for sub in edges[node]:\n",
    "                dfs(sub,trace,depth+1)\n",
    "            trace[val].pop()\n",
    "        dfs(0,[[] for _ in range(51)],0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        dep = [0] * n\n",
    "        def dfs(u, d, fa):\n",
    "            dep[u] = d\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    dfs(v, d + 1, u)\n",
    "        dfs(0, 0, -1)\n",
    "\n",
    "        cnt = [-1] * 51\n",
    "        d = [0] * n\n",
    "        vis = [0] * n\n",
    "        vis[0] = 1\n",
    "        cnt[nums[0]] = 0\n",
    "        q = deque()\n",
    "        q.append((0, cnt))\n",
    "        while q:\n",
    "            f, c = q.popleft()\n",
    "            for u in g[f]:\n",
    "                if not vis[u]:\n",
    "                    vis[u] = 1\n",
    "                    cc = c[::]\n",
    "                    d[u] = c[::]\n",
    "                    cc[nums[u]] = u\n",
    "                    q.append((u, cc))\n",
    "        \n",
    "        ans = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            de = -inf\n",
    "            for j in range(1, 51):\n",
    "                if d[i][j] != -1 and dep[d[i][j]] > de and gcd(nums[i], nums[d[i][j]]) == 1:\n",
    "                    ans[i] = d[i][j]\n",
    "                    de = dep[d[i][j]]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "up = [[j for j in range(1, 51) if gcd(i, j) == 1] for i in range(51)]\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        e = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        depth = [-1] * n\n",
    "        def getDepth(x, r, d):\n",
    "            depth[x] = d\n",
    "            d += 1\n",
    "            for y in e[x]:\n",
    "                if y != r: getDepth(y, x, d)\n",
    "        getDepth(0, -1, 0)\n",
    "        res = [-1] * n\n",
    "        def dfs(x, r, p):\n",
    "            d = near = -1\n",
    "            for i in up[nums[x]]:\n",
    "                if p[i] != -1 and depth[p[i]] > d:\n",
    "                    d = depth[p[i]]\n",
    "                    near = p[i]\n",
    "            if d != -1: res[x] = near\n",
    "            pp = p[:]\n",
    "            pp[nums[x]] = x\n",
    "            for y in e[x]:\n",
    "                if y != r: dfs(y, x, pp)\n",
    "        dfs(0, -1, [-1] * 51)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "coPrime = [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50], [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49], [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50], [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49], [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, 42, 43, 44, 46, 47, 48, 49], [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49], [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48, 50], [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49], [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50], [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50], [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50], [1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39, 41, 43, 45, 47], [1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19, 22, 23, 26, 28, 29, 31, 32, 34, 37, 38, 41, 43, 44, 46, 47, 49], [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50], [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50], [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49], [1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20, 22, 23, 25, 26, 29, 31, 32, 34, 37, 38, 40, 41, 43, 44, 46, 47, 50], [1, 3, 5, 7, 9, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 35, 37, 39, 41, 43, 45, 47, 49], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 47, 48, 49, 50], [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49], [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, 42, 43, 44, 46, 47, 48, 49], [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 41, 43, 45, 47, 49], [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50], [1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39, 41, 43, 45, 47], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50], [1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50], [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49], [1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 46, 47, 49, 50], [1, 3, 5, 7, 9, 11, 13, 15, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49], [1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, 43, 44, 46, 47, 48], [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50], [1, 3, 5, 7, 9, 11, 13, 15, 17, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49], [1, 2, 4, 5, 7, 8, 10, 11, 14, 16, 17, 19, 20, 22, 23, 25, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50], [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 42, 43, 44, 45, 46, 47, 48, 49, 50], [1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49, 50], [1, 3, 5, 7, 9, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 35, 37, 39, 41, 43, 45, 47, 49], [1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19, 22, 23, 26, 28, 29, 31, 32, 34, 37, 38, 41, 43, 44, 46, 47, 49], [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 49, 50], [1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49], [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48, 50], [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49]];\r\n",
    "vis = [False] * 100000\r\n",
    "path: list[list[int]] = [[] for _ in range(50)]\r\n",
    "\r\n",
    "def dfs(node: int, nums: list[int], conn: dict[int, set[int]], res: list[int]) -> None:\r\n",
    "    if path[nums[node] - 1]: res[node] = path[nums[node] - 1][-1]\r\n",
    "\r\n",
    "    if node in conn:\r\n",
    "        vis[node] = True\r\n",
    "        for cp in coPrime[nums[node] - 1]:\r\n",
    "            path[cp - 1].append(node)\r\n",
    "    \r\n",
    "        for nxt in conn[node]:\r\n",
    "            if not vis[nxt]:\r\n",
    "                dfs(nxt, nums, conn, res)\r\n",
    "        \r\n",
    "        for cp in coPrime[nums[node] - 1]:\r\n",
    "            path[cp - 1].pop()\r\n",
    "        vis[node] = False\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\r\n",
    "        conn: dict[int, set[int]] = dict()\r\n",
    "        for u, v in edges:\r\n",
    "            conn.setdefault(u, set())\r\n",
    "            conn.setdefault(v, set())\r\n",
    "            conn[u].add(v)\r\n",
    "            conn[v].add(u)\r\n",
    "        \r\n",
    "        res = [-1] * len(nums)\r\n",
    "        dfs(0, nums, conn, res)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "\n",
    "primes = defaultdict(set)\n",
    "\n",
    "for i in range(1, 51):\n",
    "    for j in range(i, 51):\n",
    "        if gcd(i, j) == 1:\n",
    "            primes[i].add(j)\n",
    "            primes[j].add(i)\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        dedges = defaultdict(set)\n",
    "\n",
    "        for a, b in edges:\n",
    "            dedges[a].add(b)\n",
    "            dedges[b].add(a)\n",
    "\n",
    "        visited = set()\n",
    "        def dfs(x):\n",
    "            visited.add(x)\n",
    "\n",
    "            for y in dedges[x]:\n",
    "                dedges[y].remove(x)\n",
    "                if y not in visited:\n",
    "                    dfs(y)\n",
    "\n",
    "        dfs(0)\n",
    "        n = len(nums)\n",
    "\n",
    "        ret = [-1 for i in range(n)]\n",
    "\n",
    "        def bt(x, path, pos):\n",
    "            if x > 0:\n",
    "                tmp = -1\n",
    "                for p in primes[nums[x]]:\n",
    "                    if p in pos and pos[p]:\n",
    "                        if pos[p][-1] == len(path) - 1:\n",
    "                            if len(pos[p]) > 1:\n",
    "                                tmp = max(tmp, pos[p][-2])\n",
    "                        else:\n",
    "                            tmp = max(tmp, pos[p][-1])\n",
    "                \n",
    "                if tmp != -1:\n",
    "                    ret[x] = path[tmp]\n",
    "\n",
    "            for y in dedges[x]:\n",
    "                pos[nums[y]].append(len(path))\n",
    "                path.append(y)\n",
    "                bt(y, path, pos)\n",
    "                path.pop()\n",
    "                pos[nums[y]].pop()\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        d[nums[0]].append(0)\n",
    "        bt(0, [0], d)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "prime_pair = defaultdict(set)\n",
    "for x in range(1, 51):\n",
    "    for y in range(x, 51):\n",
    "        if gcd(x, y) == 1:\n",
    "            prime_pair[x].add(y)\n",
    "            prime_pair[y].add(x)\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        graph, pre, visited, result = defaultdict(set), defaultdict(list), [True] + [False] * ((n := len(nums)) - 1), [-1] * n\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "\n",
    "        def dfs(root: int, level: int) -> NoReturn:\n",
    "            cur = recent = -1\n",
    "            for num in prime_pair[nums[root]]:\n",
    "                if pre[num] and pre[num][-1][1] > recent:\n",
    "                    cur, recent = pre[num][-1]\n",
    "            result[root] = cur\n",
    "            pre[nums[root]].append([root, level])\n",
    "            visited[root] = True\n",
    "            for son in graph[root]:\n",
    "                if not visited[son]:\n",
    "                    dfs(son, level + 1)\n",
    "            pre[nums[root]].pop()\n",
    "            visited[root] = False\n",
    "        dfs(0, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        e = defaultdict(list)\n",
    "        n = len(nums)\n",
    "        for u,v in edges:\n",
    "            e[u].append(v)\n",
    "            e[v].append(u)\n",
    "            \n",
    "        dep = [-1 for _ in range(n)]\n",
    "        dep[0] = 0\n",
    "        def dfs1(cur,fa):\n",
    "            nonlocal dep\n",
    "            for nxt in e[cur]:\n",
    "                if nxt != fa and dep[nxt] == -1:\n",
    "                    dep[nxt] = dep[cur] + 1\n",
    "                    dfs1(nxt,cur)\n",
    "            return\n",
    "        dfs1(0,-1)\n",
    "                    \n",
    "        \n",
    "        ids = [[] for _ in range(51)]\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        def dfs2(cur,fa):\n",
    "            nonlocal ans,ids,nums,dep\n",
    "            md = -1\n",
    "            v = -1\n",
    "            for i in range(1,51):\n",
    "                if ids[i] and math.gcd(i,nums[cur]) == 1:\n",
    "                    if dep[ids[i][-1]] > md:\n",
    "                        md = dep[ids[i][-1]]\n",
    "                        v = ids[i][-1]\n",
    "            ans[cur] = v\n",
    "            ids[nums[cur]].append(cur)\n",
    "            for nxt in e[cur]:\n",
    "                if nxt != fa:\n",
    "                    dfs2(nxt,cur)\n",
    "            ids[nums[cur]].pop()\n",
    "            return\n",
    "        dfs2(0,-1)\n",
    "        return ans\n",
    "                    \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        e = defaultdict(list)\n",
    "        n = len(nums)\n",
    "        for u,v in edges:\n",
    "            e[u].append(v)\n",
    "            e[v].append(u)\n",
    "            \n",
    "        dep = [-1 for _ in range(n)]\n",
    "        dep[0] = 0\n",
    "        def dfs1(cur,fa):\n",
    "            nonlocal dep\n",
    "            for nxt in e[cur]:\n",
    "                if nxt != fa and dep[nxt] == -1:\n",
    "                    dep[nxt] = dep[cur] + 1\n",
    "                    dfs1(nxt,cur)\n",
    "            return\n",
    "        dfs1(0,-1)\n",
    "                    \n",
    "        \n",
    "        ids = [[] for _ in range(51)]\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        def dfs2(cur,fa):\n",
    "            nonlocal ans,ids,nums,dep\n",
    "            md = -1\n",
    "            v = -1\n",
    "            for i in range(1,51):\n",
    "                if ids[i] and math.gcd(i,nums[cur]) == 1:\n",
    "                    if md == -1:\n",
    "                        md = dep[ids[i][-1]]\n",
    "                        v = ids[i][-1]\n",
    "                    else:\n",
    "                        if dep[ids[i][-1]] > md:\n",
    "                            md = dep[ids[i][-1]]\n",
    "                            v = ids[i][-1]\n",
    "            ans[cur] = v\n",
    "            ids[nums[cur]].append(cur)\n",
    "            for nxt in e[cur]:\n",
    "                if nxt != fa:\n",
    "                    dfs2(nxt,cur)\n",
    "            ids[nums[cur]].pop()\n",
    "            return\n",
    "        dfs2(0,-1)\n",
    "        return ans\n",
    "                    \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        d = defaultdict(set)\n",
    "        for a in set(nums):\n",
    "            for b in set(nums):\n",
    "                if math.gcd(a, b) == 1:\n",
    "                    d[a].add(b)\n",
    "                    d[b].add(a)\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        visited = set()\n",
    "        nearest = {}\n",
    "        def dfs(i, route):\n",
    "            visited.add(i)\n",
    "            ans[i] = route[nums[i]]\n",
    "            t = route[:]\n",
    "            for j in d[nums[i]]:\n",
    "                t[j] = i\n",
    "            for child in g[i]:\n",
    "                if child in visited:\n",
    "                    continue\n",
    "                dfs(child, t)\n",
    "        dfs(0, [-1] * 51)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
